\documentclass[letterpaper,12pt]{report}
\usepackage[letterpaper,paperheight=26cm, paperwidth=20cm, top=1.5cm,bottom=1.5cm, left=2cm, right=2cm]{geometry}

%definecolor{blue}{rgb}{0.25, 0.25, 0.99}
%\geometry{}
\columnseprule1pt
\columnsep0.7cm
\usepackage{makeidx}
%usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
%usepackage[T1]{fontenc}
\DeclareUnicodeCharacter{00B4}{$\acute{ }$}
%usepackage{german}
\usepackage{alltt}
\usepackage{verbatim}
\usepackage{minted}
%\setminted{bgcolor=gruen}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage[bookmarks,allcolors=blue,colorlinks]{hyperref}
\usepackage[pdftex]{color}

\definecolor{grau}{rgb}{0.95, 0.95, 0.95}
\definecolor{gelb}{rgb}{0.95, 0.95, 0.5}
\definecolor{hell}{rgb}{0.99, 0.99, 0.9}
\definecolor{rot}{rgb}{0.95, 0.8, 0.8}
\definecolor{gruen}{rgb}{0.8, 0.95, 0.8}
\definecolor{blau}{rgb}{0.8, 0.8, 0.95}
\definecolor{rgxblau}{rgb}{0.0, 0.0, 0.5}
\definecolor{trmred}{rgb}{0.2, 0.1, 0.1}

\newminted[code]{fr}{bgcolor=hell}
\newmint[exq]{fr}{bgcolor=hell}
\newmintinline[ex]{fr}{bgcolor=hell}
%newenvironment{code}[0]{\verbatim}{\endverbatim}
%newcommand{\exq}[1]{\begin{quote}\begin{code}#1\end{code}\end{quote}}
%\newcommand{\ex}[1]{\begin{code}#1\end{code}}
\newcommand{\boxquote}[3]{
\begin{center}
\colorbox{#1}%
{\parbox{0.9\textwidth}{
\sf
\underline{#2}:
#3
}}
\end{center}}

\newcommand{\colorquote}[2]{
\begin{center}
\colorbox{#1}%
{\parbox{0.9\textwidth}{
\sf
#2
}}
\end{center}}

\newcommand{\hasdiff}[1]{\boxquote{rot}{Difference to \haskell{} 98/2010}{#1}}
\newcommand{\note}[1]{\boxquote{grau}{Note}{#1}}
\newcommand{\todo}[1]{\boxquote{blau}{TODO}{#1}}
\newcommand{\trans}[1]{\boxquote{gelb}{Translation}{#1}}
\newcommand{\inmargin}[1]{\marginpar{\scriptsize\raggedright #1}}
\newcommand{\example}[1]{\boxquote{hell}{Example}{\exq{#1}}}

\newcommand{\haskell}[0]{\textsc{Haskell}}
\newcommand{\frege}[0]{\textsc{Frege}}
\newcommand{\java}[0]{\textsc{Java}}
\newcommand{\arrow}[0]{\begin{math}\rightarrow\end{math}}
\newcommand{\qq}[1]{"#1"}

\newcommand{\jex}[1]{the \java{} expression generated for \texttt{#1}}
\newcommand{\ft}[1]{\emph{\textcolor{rgxblau}{ft}}{\Large (}#1{\Large )}}
\newcommand{\jt}[1]{\emph{\textcolor{rgxblau}{jt}}{\Large (}#1{\Large )}}


\newcommand{\term}[1]{\textbf{\texttt{\textcolor{trmred}{#1}}}}
\newcommand{\regex}[1]{\texttt{\textcolor{rgxblau}{#1}}}
\newcommand{\sym}[1]{\textbf{\texttt{\textcolor{trmred}{#1}}}}
\newcommand{\gcom}[1]{{\hspace{\fill}\scriptsize (#1)}}

\newcommand{\brackz}[0]{\textbf{\texttt{\textcolor{trmred}{]}}}}
\newcommand{\bracka}[0]{\textbf{\texttt{\textcolor{trmred}{[}}}}
\newcommand{\bracea}[0]{\textbf{\texttt{\textcolor{trmred}{\{}}}}
\newcommand{\bracez}[0]{\textbf{\texttt{\textcolor{trmred}{\}}}}}

\newcommand{\nont}[1]{\textit{#1}}
\newcommand{\some}[1]{{\Large \{}#1{\Large \}}}
\newcommand{\opt}[1]{{\Large [} #1 {\Large ]}}
\newcommand{\more}[1]{#1 {\Large \{} #1 {\Large \}}}
\newcommand{\liste}[2]{#1\some{#2 #1}}
\newcommand{\rul}[1]{\nont{#1}:\\\hspace{0.5in} }
\newcommand{\alt}[0]{\\\hspace{0.5in}{\Large $|$} }
\newcommand{\oder}[0]{{\Large $|$}}
\newcommand{\checked}[1]{#1!}

\makeindex

\parindent0cm
%\oddsidemargin0.5cm
%\evensidemargin0.5cm
%\textwidth12cm
\parskip2mm
\pagestyle{headings}

\date{last changed \today{} \\ 3.21.285}
\author{\small{by Ingo Wechsung}}
\title{The \frege{} Programming Language (\emph{Draft})}

% explained that Ord T needs a hashCode implementation.
% explicated inlining
% explicated why 2 sibling subclass instantiations may not work
% clarified ambiguous instance imports.
% final (?) version of import
% corrected chaptermodules - classes can have no member lists
% listed protected an forall keywords in lex chapter
% corrected chaptermodules
% adapted chaptermodules and described new import features

\begin{document}

\maketitle


%\begingroup 
%\let\onecolumn\twocolumn 

\begin{abstract}

This document describes the functional programming language \frege{}
and its implementation
for the \java{} virtual machine. Commonplace features of \frege{} are
type inference,
lazy evaluation,
modularization and separate compile-ability,
algebraic data types and type classes,
pattern matching and list comprehension.

Distinctive features are, first, that the type system supports
\emph{higher ranked polymorphic types},
and, second,
that \frege{} code is compiled to \java{}.
This allows for maximal interoperability with existing
\java{} software.
Any \java{} class may be used as an abstract data type, \java{}
functions and methods may be called from \frege{} functions and vice
versa.

Despite this interoperability feature  \frege{} is a pure functional language as long as impure \java{} functions are declared accordingly.

\begin{center}\textbf{What is or who was Frege?}\end{center}

%\inmargin{In honor of \\G. Frege}
Friedrich Ludwig Gottlob Frege
\index{Frege! Gottlob}
was a
German mathematician, who, in the second half of the 19th
century tried to establish the foundation of mathematics in pure
logic. Although this attempt failed in the very moment when he
was about to publish his book \emph{Grundgesetze der Arithmetik},
he is nevertheless recognized as the father of modern logic among
philosophers and mathematicians.

In his essay \emph{Funktion und Begriff} \cite{f1891} Frege introduces a function that takes another function as argument and remarks:

\begin{quote}
\small{
Eine solche Funktion ist offenbar grundverschieden von den bisher betrachteten; denn als ihr Argument kann nur eine Funktion auftreten. Wie nun Funktionen von Gegenständen grundverschieden sind, so sind auch Funktionen, deren Argumente Funktionen sind und sein müssen, grundverschieden von Funktionen, deren Argumente Gegenstände sind und nichts anderes sein können. Diese nenne ich Funktionen erster, jene Funktionen zweiter Stufe.
}
\end{quote}

And, as if this was not confusing enough, he continues  later:

\begin{quote}
\small{
Man muß bei den Funktionen zweiter Stufe mit einem Argumente unterscheiden, je nachdem als dies Argument eine Funktion mit einem oder eine solche mit zwei Argumenten erscheinen kann; denn eine Funktion mit einem Argumente ist so wesentlich verschieden von einer solchen mit zwei Argumenten, daß die eine nicht an eben der Stelle als Argument auftreten kann, wo die andere es kann.
}
\end{quote}

In my opinion, this makes \emph{Frege} a very good name for a functional programming language with a strong type system.

\newpage
\begin{center}\textbf{Acknowledgments}\end{center}

Heartily thanks go to the whole functional language community and
especially to the authors and contributors of
\emph{The Haskell 98 Report} \cite{h98r} and \emph{Haskell 2010 Language Report} \cite{h2010}.
This documents structure closely reproduces that of the latter one as knowledgeable people will
easily spot.

I am especially grateful to Simon Peyton Jones, John Hughes and Philip
Wadler. By publishing their knowledge
and wisdom in numerous papers and books accessible through the internet
these men of genius enrich the world and make it a better place.
\end{abstract}

\tableofcontents

\listoftables

\listoffigures
%\endgroup

%\mainmatter

\chapter{Introduction}

%\section{The \frege{} language}

\frege{} is a strongly typed, pure functional language with non-strict evaluation for the \emph{Java Virtual Machine}. It is strongly influenced by \haskell{} and strives for maximal source code compatibility with \haskell{}. In fact, many regard \frege{} simply as the \haskell{} dialect for the JVM. 

\frege{} has the following features:

\begin{itemize}

\item haskell{} ({\tt www.haskell.org}) like syntax

\item type safety through a strong type system with type inference. The
type inference mechanism is based on and derived from the paper
\emph{Practical type inference for arbitrary-rank types} by Simon
Peyton Jones \cite{ptifart}, to whom the author is greatly indebted.

Type inference by the compiler means that it is
almost never necessary to declare the type of variables, functions or
expressions.

\item non-strict evaluation: expressions are only evaluated when they are
needed.

\item separate compilation of modules

\item rich type system with basic types, functions, regular expressions,
lists, tuples and user defined algebraic types.
In addition, types from the host language may be used as abstract
types.

\item user definable operators

\item type classes (interfaces) and instances (types that
implement interfaces) provide a form of controlled polymorphism. For
example, a sorting function may require that the values to be sorted
must support comparisons. This is also a clean and type safe way to
overload functions and operators.

\item pattern matching with guards.

\item interface to \java{}. In fact, \frege{} is
compiled to \java{} and
all primitive types and operations are borrowed from \java{}.

\end{itemize}

If you know \haskell{},
\frege{} will seem very familiar to you. 
This document contains boxes that highlight differences to \haskell{} that look like this:

\hasdiff{
Readers familiar with \haskell{} look for paragraphs like this to learn what is different in \frege{}.
}

\frege{} is

\begin{description}

\item[not object oriented]

\item[no replacement]

for already established functional programming languages like \haskell{}, Scala, Clojure, F\# and others.
Nevertheless, \frege{} may be interesting
\begin{itemize}
\item for \java{} programmers that are interested in pure functional programming. 
\item as a substitute for \haskell{} when a functional programmer needs to do work in or for the \java{} platform. 
\end{itemize}

\end{description}

\section{Differences to \haskell{} 2010}

\note{Readers not familiar with \haskell{} may want to skip this
section.}

\begin{description}
\item[Module system]
\frege{}'s module system is based on that of \java{}. A \frege{}
program is is a collection of modules. Each \frege{}
source file defines exactly one module
and compiles to a \java{} source file with the definition of a
\texttt{public class}.


\item[Types]

Numeric literals are not overloaded in \frege{}. 

\item[Strings]
Strings are primitive types in \frege{} and are implemented
as \java{}'s \texttt{java.lang.String} type.
Conversions to and
from lists of characters are provided.

\item[Regex]
\par Another primitive \frege{} type is \texttt{Regex}. It makes
powerful
and fast working functions on strings possible. A \texttt{Regex} can
also
be used as pattern for string arguments.

\end{description}


\paragraph{What \frege{} has and \haskell{} 98 does not have}
\begin{itemize}
\item support for regular expressions in the language
\item records with field labels that do not pollute the name space
\item definitions that live in the scope of a data type
\item pattern guards as proposed by Simon Peyton Jones in \cite{pguards}
and meanwhile implemented in \haskell{} 2010.
\item access to any \java{} class and its public members and methods
\end{itemize}

\section{Program structure}

In this section, we introduce the language structure and at the
same time give an outline of the organization of this
document.

\begin{enumerate}

\item At the topmost level, a \frege{} program is a set of
\emph{modules}, described in \autoref{modules}.

\item A module consists of a collection of
\emph{declarations},
of which there are several kinds, all described in
\autoref{declarations}.
Declarations define things such as ordinary values and functions,
data types,
type classes, fixity information.

\item At the next lower level are \emph{expressions}, described in
\autoref{expressions}.

\item At the bottom level is the lexical structure, described in
\autoref{lexical structure}.

\end{enumerate}

The last chapter of this book describes  the native interface
(\autoref{native interface}).
%Also there are several appendices.

Examples of \frege{} program fragments in running text are given in
typewriter font. Sometimes examples are given in a form of
colored pseudo code,
with indexed identifiers in \emph{italics} as in \term{if} $e_1$
\term{then} $e_2$ \term{else} $e_3$, where the  italicized names are
supposed to be mnemonic, such as $e$ for expressions, $p$ for patterns,
etc.


\input{chapterlex}
\input{chapterexpr}
%\input{chapterdeclarations}
%\input{chaptermodules}
%\input{chaptertypes}
%\input{chapterio}
%\input{chapternative}
%\input{chapterderived}

\appendix


\begin{thebibliography}{99}

\bibitem{f1891} Gottlob Frege \emph{Funktion und Begriff} 
\small{Vortrag, gehalten in der Sitzung vom 9.1.1891 der Jenaischen Gesellschaft für Medizin und Naturwissenschaft}

\bibitem{h98r} Simon Peyton Jones,
John Hughes et al. \emph{Report on the Programming Language
Haskell 98}

\bibitem{h2010} Simon Marlow (editor) \emph{Haskell 2010 Language Report}

\bibitem{ptifart} Simon Peyton Jones \emph{Practical type
inference for arbitrary-rank types}

\bibitem{lsnbg} Simon Peyton Jones, et al. \emph{Let Should Not Be Generalised}

\bibitem{langspec3} James Gosling, Bill Joy, Guy Steele and
Gilad Bracha. \emph{The Java Language Specification Third
Edition}

\bibitem{implfun} Simon Peyton Jones. \emph{The Implementation of
Functional Programming Languages}

\bibitem{pguards} Martin Erwig, Simon Peyton Jones. \emph{Pattern
Guards and Transformational Patterns}

\bibitem{apidoc} \emph{Java 2 Platform API Specification}

\bibitem{lazyst} John Launchbury, Simon Peyton Jones \emph{Lazy Functional State Threads}

\end{thebibliography}

%\begin{theindex}

\printindex

%\end{theindex}

\end{document}
